﻿// 0920train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using namespace std;

/*
 小华负责公司知识图谱产品，现在要通过新词挖掘完善知识图谱
新词挖掘：给出一个待挖掘文本内容字符串content和一个词的字符串word
找到content中所有word的新词
新词：使用词word的字符排列形成的字符串
请帮小华实现新词挖掘，返回发现的新词的数量

输入描述
第一行输入为待挖掘的文本内容content；
第二行输入为词word；

输出描述
在中找到的所有word的新词的数量

输入
qweebaewqd
qwe
输出
2
起始索引等于 0 的子串是 qwe, 它是 word的新词
起始索引等于 6 的子串是 ewq, 它是 word的新词
 */
class Solution01
{
public:
    Solution01(string&origin_str, string&sub_str)
    {
        if (sub_str.size()>origin_str.size())
        {
            cout << 0;
            return;
        }

        int target_size = sub_str.size();
        vector<int>statistic_v(128);

        for (auto&ch:sub_str)
        {
            statistic_v[ch] += 1;
        }

        vector<int>result_i;
        string first_sub = origin_str.substr(0, target_size);
        int curr_size = target_size;
        for (int i=0; i< target_size; i++)
        {
            char ch = first_sub[i];
            if (statistic_v[ch]>0)
            {
                curr_size -= 1;
            }
            statistic_v[ch] -= 1;
            if (curr_size == 0) result_i.push_back(0);
        }

        int old_left = 0;
        int total_size = origin_str.size();
        for (int left=1,right=target_size; right< total_size; left++,right++)
        {
            char last_ch = origin_str[old_left];
            if (statistic_v[last_ch]>=0)
            {
                curr_size += 1;
            }
            statistic_v[last_ch] += 1;

            char new_ch = origin_str[right];
            if (statistic_v[new_ch]>0)
            {
                curr_size -= 1;
            }
            statistic_v[new_ch] -= 1;

            if (curr_size==0)
            {
                string curr_sub = origin_str.substr(left, target_size);
                result_i.push_back(left);
            }

            old_left = left;
            //for
        }

        cout << result_i.size();
	    //Solution01
    }
};


/*
不存在多重引用<>的情况，一个单元格只能引用一个其他单元格。比如下面这种场景是不存在的：
A单元格：C
B单元格： kAydzqo
C单元格： y<A><B>d
D单元格： y<<A>>d

1,2<A>00
 */
class Solution02
{
public:
    vector<string>checkStr(string&total_str, int index)
    {
        vector<string>empty_v;
        vector<string>result;

        int para_count = 0;
        bool is_left = false;
        string curr_str;
        unordered_set<char>replace_ch;
        int total_str_size = total_str.size();
        for (auto&ch:total_str)
        {
            if (ch=='<')
            {
                is_left = true;
                para_count += 1;
                //不能嵌套
                if (para_count > 1) return empty_v;
                //前面字符先入数组
                if (!curr_str.empty())
                {
                    result.push_back(curr_str);
                    curr_str = "";
                }
                continue;
            }

            if (ch=='>')
            {
                is_left = false;
                para_count -= 1;
                continue;
            }

            if (is_left)
            {
                bool isBigCh = ch >= 'A' && ch <= 'Z';
                if (!isBigCh) return empty_v;

                //字符是括号里的
                replace_ch.insert(ch);
                //不能引用多重
                if (replace_ch.size() > 1) return empty_v;

                if (replace_map.count(ch) == 0)
                {
                    //先占个位置
                    replace_map[ch] = {};
                }

                string ch_str;
                ch_str += ch;
                result.push_back(ch_str);
                int result_size = result.size();
                replace_pos[index].insert(result_size-1);
            }
            else
            {
	            //字符不是括号里的
                curr_str += ch;
            }
            //for
        }

        if (para_count != 0) return empty_v;
        if (!curr_str.empty())
        {
            result.push_back(curr_str);
        }
        return result;
        //checkStr
    }

    bool checkReCh(int layer, int index)
    {
        return replace_pos[layer].count(index) > 0;

    }

    void bfs(deque<char>&bfs_queue)
    {
        while (!bfs_queue.empty())
        {
            char top_node = bfs_queue.front();
            bfs_queue.pop_front();

            for (auto&ch:linked_map[top_node])
            {
                indegree_map[ch] -= 1;
                //入度为0入队列
                if (indegree_map[ch]==0)
                {
                    bfs_queue.push_back(ch);
                }
            }

        }

        //bfs
    }

    string getReplace(char oh_char)
    {
        int layer = oh_char - 'A';
        vector<string>curr_v = cache_v[layer];

        string curr_str;
        int curr_v_size = curr_v.size();
        for (int i=0; i< curr_v_size; i++)
        {
            string str_item = curr_v[i];
	        if (str_item.size()==1 && checkReCh(layer, i))
	        {
                string re_str = getReplace(str_item[0]);
                curr_str += re_str;
	        }
            else
            {
                curr_str += str_item;
            }
        }
        return curr_str;
	    //getReplace
    }

    Solution02(vector<string>&origin_v)
    {
        int origin_v_size = origin_v.size();
        for (int i=0; i<origin_v_size; i++)
        {
            string str = origin_v[i];
            vector<string>str_v = checkStr(str, i);
            if (str_v.empty())
            {
                cout << -1;
                return;
            }
            cache_v.push_back(str_v);
        }


        for (auto&map_item:replace_map)
        {
            char key = map_item.first;
            int layer = key - 'A';
            if (layer>cache_v.size()-1)
            {
                cout << -1;
                return;
            }

            map_item.second = cache_v[layer];

            //更新linked_map
            vector<string>curr_v = cache_v[layer];
            int v_size = curr_v.size();
            for (int i=0; i<v_size; i++)
            {
                string str = curr_v[i];
                if (str.size() == 1 && checkReCh(layer, i))
                {
                    indegree_map[str[0]] += 0;
                    indegree_map[key] += 1;
                    linked_map[str[0]].insert(key);
                }
            }
            //for
        }

        deque<char>bfs_queue;
        //入度为0的节点入队列
        for (auto&map_item:indegree_map)
        {
            if (map_item.second == 0) bfs_queue.push_back(map_item.first);
        }
        bfs(bfs_queue);

        for (auto&map_item:indegree_map)
        {
	        if (map_item.second !=0)
	        {
                cout << -1;
                return;
	        }
        }

        vector<string>result_v;
        //递归迭代，还原字符
        int cache_size = cache_v.size();
        for (int layer=0; layer<cache_size; layer++)
        {
            vector<string>str_v = cache_v[layer];
            string curr_str;
            int str_v_size = str_v.size();
	        for (int i=0; i<str_v_size;i++)
	        {
                string str_item = str_v[i];
		        if (str_item.size()==1 && checkReCh(layer,i))
		        {
                    string re_str = getReplace(str_item[0]);
                    curr_str += re_str;
		        }
                else
                {
                    curr_str += str_item;
                }
                
	        }
            result_v.push_back(curr_str);
        }

        for (int i=0; i<result_v.size(); i++)
        {
            cout << result_v[i];
	        if (i!=result_v.size()-1)
	        {
                cout << ',';
	        }
        }

        //Solution02
    }
private:
    vector<vector<string>>cache_v;
    unordered_map<int, unordered_set<int>>replace_pos;
    unordered_map<char, vector<string>>replace_map;
    unordered_map<char, unordered_set<char>>linked_map;
    unordered_map<char, int>indegree_map;
};


int main()
{
	{
        //<C>12,<A>12,13
        string origin_str;
        cin >> origin_str;

        vector<string>origin_v;
        stringstream oh_sstream(origin_str);
        string token;
        while (getline(oh_sstream,token,','))
        {
            origin_v.push_back(token);
        }

        Solution02 solu(origin_v);
        return 0;
	}
    string origin_str, sub_str;
    cin >> origin_str >> sub_str;

    Solution01 solu(origin_str, sub_str);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
